Huyện Phù Yên vốn là huyện lâu đời nhất của tỉnh Sơn La. Phù Yên thời Nhà Lý đặt tên là châu Phù Hoa đến thời Nguyễn, năm Thiệu Trị thứ nhất năm 1814 đổi tên là châu Phù Yên. Giai đoạn 1955-1962 thuộc khu tự trị Thái - Mèo. Giai đoạn 1962-1975 thuộc tỉnh Nghĩa Lộ.

Sau năm 1975, khu tự trị Tây Bắc bị giải thể, huyện Phù Yên chuyển từ tỉnh Nghĩa Lộ về tỉnh Sơn La quản lý, gồm thị trấn Vạn Yên và 25 xã: Bắc Phong, Đá Đỏ, Gia Phù, Huy Bắc, Huy Hạ, Huy Tân, Huy Thượng, Huy Tường, Kim Bon, Mường Bang, Mường Cơi, Mường Do, Mường Lang, Mường Thải, Nam Phong, Quang Huy, Quang Minh, Suối Bau, Suối Tọ, Tân Phong, Tường Hạ, Tường Phong, Tường Phù, Tường Thượng, Tường Tiến.

Ngày 13 tháng 4 năm 1977, thành lập thị trấn Phù Yên, thị trấn huyện lị huyện Phù Yên và giải thể thị trấn Vạn Yên.

Ngày 25 tháng 7 năm 1978, đổi tên xã Quang Minh thành xã Sập Xa.[1]

Ngày 16 tháng 1 năm 1979, chia xã Mường Lang thành hai xã lấy tên là xã Tân Lang và xã Mường Lang.

Huyện Phù Yên có 1 thị trấn và 26 xã như hiện nay.